package com.cet.qz.unit01.chapter1_2;

import edu.princeton.cs.algs4.Counter;
import edu.princeton.cs.algs4.StdIn;

/**
 * @program: algorithm
 * @description:
 * @author: 陈恩涛
 * @create: 2021-03-03 21:37
 **/
public class Qz1_2_9 {

    public static int rank(int key, int[] a, int lo, int hi, Counter counter) {
        if (lo > hi) {
            return -1;
        }
        int mid = lo + (hi - lo) / 2;
        counter.increment();
        if (a[mid] == key) {
            return mid;
        } else if (a[mid] > key) {
            return rank(key, a, lo, mid - 1, counter);
        } else {
            return rank(key, a, mid + 1, hi, counter);
        }
    }

    public static int rank(int key, int[] a, Counter counter) {
        return rank(key, a, 0, a.length - 1, counter);
    }

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,6,7,8,9};
        System.out.println("请输入要查找的值：");
        int key = StdIn.readInt();
        Counter counter = new Counter("统计二分查找次数");
        if (rank(key, a, counter) == -1) {
            System.out.println("经过" + counter.tally() + "次检查，发现" + key + "不在该数组中");
        } else {
            int position = rank(key,a,counter) +1;
            System.out.println("经过" + counter.tally() + "次检查，发现" + key + "在数组的第"+position+"位");
        }
    }
}
